﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text
{
    /// <summary>
    /// 关于排序的一些算法总结
    /// </summary>
    public class SortWay
    {
        /// <summary>
        /// 冒泡排序 :相邻元素之间的比较和交换
        /// </summary>
        /// <returns></returns>
        public void bubbleSort(int[] arr)
        {
            int n = arr.Length,temp;
            for (int i = 0; i < n; i++)
            {
                //flag = 0;
                for (int j = n-1; j >=i+1; j--)
                {
                    if (arr[j]<arr[j-1])
                    {
                        temp = arr[j - 1];
                        arr[j - 1] = arr[j];
                        arr[j] = temp;
                        //flag = 1;
                    }
                }
                //Console.WriteLine();
                //Console.WriteLine("---当i="+i+"时:");
                //for (int g = 0; g < n; g++)
                //{
                //    Console.Write(arr[g]+" ");
                //}
                //if (flag == 0) return;
            }
        }
        /// <summary>
        /// 直接插入排序:每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的序列中的适当位置，直到全部记录插入完成为止。
        /// 把数据分为两个区:有序区,无序区,跟起扑克牌类似
        /// https://cloud.tencent.com/developer/article/1441430 //具体图解
        /// </summary>
        /// <param name="arr"></param>
        public void directInsertSort(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)//第一个元素默认为有序序列,从第一个元素开始将无序数列的元素
            {
                if (arr[i] < arr[i-1])
                {
                    //取出 无序数列的第一个元素作为被插入元素
                    var guard = arr[i];
                    //记住有序数列    的最后一个位置并将有序数列的位置扩大一个
                    var j = i - 1;
                    arr[i] = arr[j];
                    //找到被插入元素所在的位置
                    while (j>=0&&guard<arr[j])
                    {
                        arr[j + 1] = arr[j];
                        j--;
                    }
                    //将元素插入有序序列
                    arr[j + 1] = guard;
                }
                //Console.WriteLine();
                //Console.WriteLine("---当i=" + i + "时:");
                //for (int g = 0; g < arr.Length; g++)
                //{
                //    Console.Write(arr[g] + " ");
                //}
            }
        }
        /// <summary>
        /// 直接选择排序:每一趟从待排序的记录中选出关键字最小的记录，顺序放入已排序数列的最后，直到全部记录排序完毕。
        /// 常用的选择排序方法有直接选择排序和堆排序。
        /// *会把无序数列的最小元素插入到当前的i中
        /// https://cloud.tencent.com/developer/article/1441430 //具体图解
        /// </summary>
        /// <param name="arr"></param>
        public void directCheckSort(int[] arr)
        {
            var n = arr.Length;
            for (int i = 0; i < n; i++)
            {
                var key = i;//记录当前无序序列的最小值下标

                //找出无序数列中的最小值
                for (int j = i+1; j < n; j++)
                {
                    if (arr[j]<arr[key])
                    {
                        key = j;//当前最小的下标   替换
                    }
                }

                if (key!=i)//找到最小值了,将最小值插入有序队列
                {
                    var swap = arr[i];
                    arr[i] = arr[key];
                    arr[key] = swap;
                }
            }
        }
    }
}
